package it.storm.solution;

import java.util.Arrays;

/**
 * 1122. 数组的相对排序
 * https://leetcode-cn.com/problems/relative-sort-array/
 */
public class Solutions_1122 {
    public static void main(String[] args) {
        int[] arr1 = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = {2, 1, 4, 3, 9, 6};  // output: {2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19}

        int[] result = relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(result));
    }

    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] res = new int[arr1.length];
        int[] bucket = new int[1001];
        // 遍历 arr1，将 arr1 中的元素，加入到桶中
        for (int num : arr1) {
            bucket[num] ++;
        }
        int idx = 0;
        // 遍历 arr2，将存在于 arr1 中的元素（即 bucket[num] > 0），进行“排序”
        for (int num : arr2) {
            while (bucket[num] > 0) {
                res[idx ++] = num;
                bucket[num] --;
            }
        }
        // 再次遍历 bucket，若 bucket[i] > 0，即说明该数值不存在于 arr2 中
        for (int i = 0; i < 1001; i++) {
            while (bucket[i] > 0) {
                res[idx ++] = i;
                bucket[i] --;
            }
        }
        return res;
    }
}
